With computerization of business core in enterprises and the like, most enterprises have a large scale database to contain a great amount of data used for business purposes. Because these pieces of data are important for their businesses and because of the aspect of personal information protection, they should never leak out to the outside. For this reason, it is often the case that, in such a large scale database, data contained therein is encrypted.
A database can be regarded as a set of a large number of tables. Hereinafter, a description will be given of an encryption method described in NPL 1, which is called a searchable encryption and is used in a database wherein data contained therein is encrypted (hereafter, referred to as an encrypted database), for the purpose of linking between two tables without decrypting individual elements.
In this method, a cryptographic hash function Hash and a common key cryptography (Enc, Dec) are used. When a plaintext is expressed by m and an encryption key is expressed by k, the encryption function Enc generates a cryptogram c by c=Enc(k, m), and when the cryptogram is c and the encryption key is expressed by k, the decryption function Dec decrypts the cryptogram c by m=Dec(k, c).
The searchable encryption encrypts a plaintext m as shown by a following equation 1 by using a set of secret keys (K, k). Its decryption can be processed in the form of a following equation 2.C:=(C[1],C[2])=(Hash(K,m),Enc(k,m))  [Equation 1]m=Dec(k,C[2])  [Equation 2]
In this method, when the plaintexts m are same, the first elements C[1] of cryptograms are always same. That is, determination of identity between plaintexts is possible without decrypting their cryptograms, and accordingly, natural linking between tables in terms of the same elements becomes possible.
FIGS. 9 and 10 are explanatory diagrams showing data in tables before linking, in the searchable encryption method, which is an existing technology. FIG. 9 shows a table “I” 901, and FIG. 10 shows a table “II” 902. The table “I” 901 has a column “IA” 901a and a column “IB” 901b, and the table “II” 902 has a column “IIB” 902a and a column “IIC” 902b. 
FIG. 11 is an explanatory diagram showing a table “III” 903 which is obtained by linking the table “I” 901 shown in FIG. 9 with the table “II” 902 shown in FIG. 10. Because a column “IB” 901b in the table “I” 901 and a column “IIB” 902a in the table “II” 902 are each a column for “card number”, it is possible to link the tables with each other by a condition of column “IB”=column “IIB” (by linking a piece of data having an element value in the column “IB” with a piece of data having the same element value in the column “IIB”), and by that way, the table “III” 903 can be obtained.
FIG. 12 is an explanatory diagram showing a table “III′” 904 which is obtained by extracting a row having a value “Ueda” in the column “IA (name)” from the table “III” 903 shown in FIG. 11. In the above-described process, individual elements in the tables “I” 901 and “II” 902 are not encrypted.
However, the above-described process practically needs to be performed in a state where the individual elements are encrypted, without decrypting the individual elements. To enable it, it is necessary to make it possible to determine whether or not an element value in the column “IB” is the same as that in the column “IIB”. Then, the above-described encryption method referred to as the searchable encryption is used.
FIGS. 13 and 14 are explanatory diagrams showing, respectively, an encrypted table “I” 911 and an encrypted table “II” 912, which are obtained by encrypting the table “I” 901 shown in FIG. 9 and the table “II” 902 shown in FIG. 10, respectively, by the searchable encryption. In the encrypted table “I” 911 and the encrypted table “II” 912, each element is encrypted according to the above-described equation 1 by using the set of secret keys (K, k).
FIG. 15 is an explanatory diagram showing an encrypted table “III” 913 which is obtained by linking the encrypted table “I” 911 shown in FIG. 13 with the encrypted table “II” 912 shown in FIG. 14. In order to link the encrypted table “I” 911 with the encrypted table “II” 912, it is necessary to determine whether or not an element value in the column “IB” 901b is the same as that in the column “IIB” 902a before encrypted.
According to the searchable encryption, because it is possible to determine whether or not m and m′ before the encryption are equal by determining whether or not Hash(K, m) and Hash(K, m′) from encrypted elements are equal, the same can be determined, the encrypted table “III” 913 can be obtained by that way.
FIG. 16 is an explanatory diagram showing an encrypted table “III” 914 obtained by extracting a row having a value “Hash(K, Ueda)” in the column “IA (name)” from the encrypted table “III” 913 shown in FIG. 15. As mentioned above, the encrypted table “III” 914 can be obtained without decrypting the individual elements so far. A right user having the set of secret keys (K, k) can know the element, which is the “expiration date” of a credit card held by “Ueda” in this case, in the column “IIC” 902b related to this.
As other technical documents related to the above-described technology, the following ones will be mentioned. PTL 1 describes a relational database in which, using an index table obtained by generating ranking of items and encrypting it, a range search can be performed in a state where the items are kept encrypted. PTL 2 describes an encrypted database search device which performs a matching process in a state where a keyword is kept encrypted.
PTL 3 describes a technology which generates an index file using an encrypted keyword and thereby enables searching an encrypted file. PTL 4 and PTL 5 each describe a technology which reduces a time required for table linking in a distributed database system.